#include <iostream>
#include <list>
#include <queue>
#include <vector>
using std::cout;
using std::endl;

// 无向图
class Graph {
 public:
  // 默认顶点从0到n-1
  Graph(int vertexCount) { gra_.resize(vertexCount); }

  void AddEdge(int p0, int p1) {
    if (p0 >= gra_.size() || p1 >= gra_.size()) {
      return;
    }
    // 没检查重复
    gra_[p0].push_back(p1);
    gra_[p1].push_back(p0);
  }

  void Show() {
    for (int i = 0; i < gra_.size(); ++i) {
      cout << '#' << i << ": ";
      for (auto& item : gra_[i]) {
        cout << item << " ";
      }
      cout << endl;
    }
  }

  // 广度优先搜索（Breadth-First-Search）
  void Bfs(int from, int to) {
    cout << "Bfs: ";
    std::vector<bool> visited(gra_.size(), false);  // 是否访问过
    std::vector<int> prev(gra_.size(), -1);         // 前驱
    std::queue<int> vque;                           // 访问队列
    vque.push(from);
    while (!vque.empty()) {
      int i = vque.front();
      vque.pop();
      for (auto& j : gra_[i]) {
        if (!visited[j]) {
          prev[j] = i;
          if (j == to) {
            Print(prev, from, to);
            cout << endl;
            return;
          }
          visited[j] = true;
          vque.push(j);
        }
      }
    }
  }

  void Print(const std::vector<int>& prev, int from, int to) {
    if (to != -1 && from != to) {
      Print(prev, from, prev[to]);
    }
    cout << to << ' ';
  }

 private:
  std::vector<std::list<int>> gra_;
};

void TestGraph() {
  Graph graph(8);
  graph.AddEdge(0, 1);
  graph.AddEdge(0, 3);
  graph.AddEdge(1, 2);
  graph.AddEdge(1, 4);
  graph.AddEdge(3, 4);
  graph.AddEdge(2, 5);
  graph.AddEdge(4, 5);
  graph.AddEdge(4, 6);
  graph.AddEdge(5, 7);
  graph.AddEdge(6, 7);
  /*
    0-1-2
    | | |
    3-4-5
      | |
      6-7
  */

  graph.Show();

  graph.Bfs(0, 6);
}

int main() { TestGraph(); }